// test.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//date:20210324 pm12:57
#include<math.h>
#include <iostream>
using namespace std;
class Solution {
public:
	int min(int a, int b)
	{
		if (a > b)
		{
			return b;

		}
		else
		{
			return a;
		}
	}
	int minDays(int n) {
		int i, j;
		int x, y;
		n++;
		int* A = new int[n];

		for (i = 0; i < n; i++)
		{
			if (i < 4)
			{
				if (i == 0)
				{
					A[i] = 0;
					continue;
				}
				if (i == 1)
				{
					A[i] = 1;
					continue;
				}
				if (i == 2)
				{
					A[i] = 2;
					continue;
				}
				if (i == 3)
				{
					A[i] = 2;
					continue;
				}
			}
			else
			{
				if (i == n - 1)
				{
					continue;
				}
				x = i % 2;
				y= i % 3;
				if (!x )
				{
					if (!y)
					{
						A[i] = min(min(A[i / 2] + 1, A[i - 1] + 1), min(A[i - ((i / 3) * 2)] + 1, A[i - 1] + 1));

					}
					else
					{
						A[i] = min(A[i / 2] + 1, A[i - 1] + 1);
					}
					

				}
				else if ( !y)
				{
					A[i] = min(A[i-((i / 3) * 2)] + 1, A[i - 1] + 1);
				}
				else
				{
					A[i] = A[i - 1] + 1;
				}
			}

		}
		return A[n-1];
	}
	int minDays1(int n) {
		int i, j;
		int x, y;
		n++;
		i = n;

			if (i == 0)
			{
				return 0;
				
			}
			if (i == 1)
			{
				return 1;
				
			}
			if (i == 2)
			{
				return 2;
				
			}
			if (i == 3)
			{
				return 2;
				
			}
			else
			{
				x = i % 2;
				y = i % 3;
				if (!x)
				{
					if (!y)
					{
						return min(min(minDays1(i / 2) + 1, minDays1(i -1) + 1), min(minDays1(i - ((i / 3) * 2)) + 1, minDays1(i - 1) + 1));

					}
					else
					{
						return min(minDays1(i / 2) + 1, minDays1(i - 1) + 1);
					}


				}
				else if (!y)
				{
					return min(minDays1(i - ((i / 3) * 2)) + 1, minDays1(i - 1) + 1);
				}
				else
				{
					return minDays1(i - 1) + 1;
				}
			}

		
		
	}
};
int main() {
	Solution *s = new Solution();
	cout << s->minDays1(10);
}